#ifndef DEQUEMIN_H
#define DEQUEMIN_H

#include <iostream>
#include <stack>
#include <cassert>


using namespace std;

template <typename T>
class DequeWithMin
{
public:
    DequeWithMin(){
        minindex=-1;
    };
    virtual ~DequeWithMin(){};
public:
    void push_back(T val)
    {
        pushS.push(val);
        if(minindex==-1)
        {
            minpushS.push(10000+pushS.size());
            minindex=0;
        }
        else
        {
            if(val<get_min())
                minpushS.push(10000+pushS.size());
            else
            {
                bool flag1=minpushS.empty();
                bool flag2=minpopS.empty();
                assert(!flag1 || !flag2);
                int t1,t2;
                if(flag1)
                {
                    minpushS.push(minpopS.top());
                }
                else if(flag2)
                {
                    minpushS.push(minpushS.top());
                }
                else
                {
                    t1=minpushS.top();
                    t2=minpopS.top();
                    if(t1/10000==2)
                    {
                        minpushS.push(minpopS.top());
                    }
                    else
                    {
                        T ta=minpushS[t1%10000-1];
                        T tb=minpopS[t2%10000-1];
                        if(ta<tb)
                            minpushS.push(minpushS.top());
                        else
                            minpushS.push(minpopS.top());
                    }
                }
            }
        }
    };
    T pop_front()
    {
        if(!popS.empty())
        {
            T ret=popS.top();
            popS.pop();
            minpopS.pop();
            return ret;
        }
        else
        {
            while(!minpushS.empty())
                minpushS.pop();
            while(!pushS.empty())
            {
                T temp=pushS.top();
                popS.push(temp);
                pushS.pop();
                if(temp<get_min())
                    minpopS.push(20000+popS.size());
                else
                    minpopS.push(minpopS.top());
            }
            T ret=popS.top();
            popS.pop();
            minpopS.pop();
            return ret;
        }
    };
    T get_min()
    {
        bool flag1=minpushS.empty();
        bool flag2=minpopS.empty();
        assert(!flag1 || !flag2);
        int t1,t2;
        if(flag1)
        {
            t2=minpopS.top();
            return minpopS[t2%10000-1];
        }
        else if(flag2)
        {
            t1=minpushS.top();
            return minpushS[t1%10000-1];
        }
        t1=minpushS.top();
        t2=minpopS.top();
        if(t1/10000==2)
        {
            return minpopS[t2%10000-1];
        }
        else
        {
            T ta=minpushS[t1%10000-1];
            T tb=minpopS[t2%10000-1];
            return ta<tb?ta:tb;
        }
    };
private:
    stack<T> pushS;
    stack<T> popS;
    stack<int> minpushS;
    stack<int> minpopS;
    int minindex;
};
#endif